package leetcode_501_600;

import java.util.Arrays;

public class LeeCode_600 {
    public static void main(String[] args) {
        System.out.println(findIntegers(5));
        System.out.println(findIntegers(1));
        System.out.println(findIntegers(2));
    }
    private static int findIntegers(int n) {
        char[] s = Integer.toBinaryString(n).toCharArray();
        int len = s.length;
        int[][] memo = new int[len][2];
        for (int i = 0; i < len; i++) {
            Arrays.fill(memo[i], -1);
        }
        return f(s, 0, 0, true, memo);
    }
    private static int f(char[] s, int i, int pre, boolean isLimit, int[][] memo){
        if (i == s.length){
            return 1;
        }
        if (!isLimit && memo[i][pre] != -1){
            return memo[i][pre];
        }
        int res = 0, up = isLimit ? s[i] - '0' : 1;
        for (int j = 0; j <= up; j++) {
            if (pre == 1 && j == 1)
                continue;
            res += f(s, i + 1, j, isLimit && j == up, memo);
        }
        if (!isLimit)
            memo[i][pre] = res;
        return res;
    }
}
